// 示例 1：

// 输入：nums = [1, 2, 0]
// 输出：3
// 解释：范围[1, 2] 中的数字都在数组中。
// 示例 2：

// 输入：nums = [3, 4, -1, 1]
// 输出：2
// 解释：1 在数组中，但 2 没有。
// 示例 3：

// 输入：nums = [7, 8, 9, 11, 12]
// 输出：1
// 解释：最小的正数 1 没有出现。

nums = [3, 4, -1, 1]

// var firstMissingPositive = function (nums) {
//     // let len = nums.length
//     // for (let i = 0; i < len; i++) {
//     //     while (nums[i] >= 1 && nums[i] <= len && nums[nums[i] - 1] !== nums[i]) {
//     //         [nums[i], nums[nums[i] - 1]] = [nums[nums[i] - 1], nums[i]]
//     //     }
//     // }
//     const n = nums.length;
//     for (let i = 0; i < n; i++) {
//         while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
//             [nums[i], nums[nums[i] - 1]] = [nums[nums[i] - 1], nums[i]];
//         }
//     }
//     for (let i = 0; i < n; i++) {
//         if (nums[i] !== i + 1) {
//             return i + 1;
//         }
//     }
//     return n + 1;
// };

var firstMissingPositive = function (nums) {
    // 关键点：最小的未出现的正整数一定在1到n+1之间，n为数组长度。
    let len = nums.length;

    for (let i = 0; i < len; i++) {
        while (nums[i] >= 1 && nums[i] <= len && nums[i] !== nums[nums[i] - 1]) {
            const temp = nums[i];
            nums[i] = nums[temp - 1];
            nums[temp - 1] = temp;
        }
    }

    for (let i = 0; i < len; i++) {
        if (nums[i] !== i + 1) {
            return i + 1;
        }
    }
    return len + 1;
}

console.log(firstMissingPositive(nums));
